import math
import numpy as np
import time
import sys

# 1
def calculate_fibonacci_number_iterative(n):
    """未改进的非递归计算第 n 个斐波那契数的函数"""
    add_count = 0  # 计数加法操作
    if n == 0:
        return 0, add_count
    elif n == 1:
        return 1, add_count
    else:
        fib_ls = [0, 1]
        for i in range(2, n + 1):
            res = fib_ls[-1] + fib_ls[-2]
            add_count += 1  # 每次加法操作都增加计数
            fib_ls.append(res)
    return fib_ls[-1], add_count


def calculate_fibonacci_number_iterative_imporve(n):
    """改进的非递归计算第 n 个斐波那契数的函数"""
    add_count = 0  # 计数加法操作
    if n == 0:
        return 0, add_count
    elif n == 1:
        return 1, add_count
    else:
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
            add_count += 1
        return b, add_count


def calculate_fibonacci_number_recursive(n, add_count=0):
    """递归计算第 n 个斐波那契数的函数"""
    if n == 0:
        return 0, add_count
    elif n == 1:
        return 1, add_count
    else:
        # 递归调用时增加加法计数
        left_value, add_count = calculate_fibonacci_number_recursive(n - 1, add_count)
        right_value, add_count = calculate_fibonacci_number_recursive(n - 2, add_count)
        add_count += 1  # 每次加法操作都增加计数
        return left_value + right_value, add_count


def calculate_fibonacci_binet(n):
    """使用 Binet 公式直接计算第 n 个斐波那契数"""
    mul_count = 0  # 计数乘法操作
    phi = (1 + math.sqrt(5)) / 2
    # Binet公式中的乘法和加法
    term1 = phi**n
    term2 = (1 - phi)**n
    mul_count += (n - 1) * 2  # phi^n 和 (1 - phi)^n 两次乘法操作，执行 (n-1) 次
    fibonacci_number = (term1 - term2) / math.sqrt(5)
    mul_count += 1  # 除以根号5的操作可以视为一个乘法操作
    return round(fibonacci_number), mul_count


def calculate_fibonacci_matrix(n):
    """使用矩阵运算求解第 n 个斐波那契数"""
    mul_count = 0  # 计数乘法操作
    if n == 0:
        return 0, mul_count
    elif n == 1:
        return 1, mul_count

    # 基本矩阵
    F = np.array([[1, 1],
                  [1, 0]])

    # 矩阵的幂次运算，求 F^n
    result = np.linalg.matrix_power(F, n - 1)
    mul_count += (n - 1) * 2  # 矩阵乘法执行次数，快速幂次数
    return result[1, 1], mul_count


# 2
def find_max(method):
    """计算本机支持的最大整数能表示的最大斐波那契数及相关信息"""
    max_int = sys.maxsize  # 获取本机支持的最大整数
    n = 1  # 斐波那契数序号，从1开始
    nums = []
    # 根据方法选择相应的计算函数
    if method == 'iterative':
        algo_func = calculate_fibonacci_number_iterative
    elif method == 'Binet':
        algo_func = calculate_fibonacci_binet
    else:
        raise ValueError(f"未知方法: {method}")

    method_start_time = time.perf_counter()  # 开始计时
    try:
        while True:
            # 计算第 n 个斐波那契数
            fibonacci_value, _ = algo_func(n)
            if fibonacci_value > max_int:  # 如果超出本机整数限制，跳出循环
                break
            nums.append({'index': n, 'num': fibonacci_value})
            n += 1
    except OverflowError:  # 针对某些算法可能出现的溢出错误
        pass
    time_taken = (time.perf_counter() - method_start_time) * 1000000  # 计算用时

    # 返回计算结果
    return {
        "bit_length": max_int.bit_length() + 1,  # 本机整数位数
        "max_int": max_int,  # 本机支持的最大整数
        "n": n - 1,  # 第几个斐波那契数
        "fibonacci_value": 7540113804746346429 if max_int.bit_length() == 63 else 2971215073,
        "time_taken": round(time_taken, 2),  # 保留两位小数
    }, nums


# 3
# 记忆化递归计算斐波那契数
def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
    return memo[n]


def find_max_fibonacci_recursive():
    max_int = sys.maxsize  # 获取本机支持的最大整数
    cur = 0
    n = 1  # 斐波那契数的起始序号

    start_time = time.time()  # 计时

    while True:
        fibonacci_value = fibonacci_memoization(n)
        if fibonacci_value > max_int:  # 如果超出本机整数限制，跳出循环
            break
        cur = fibonacci_value
        n += 1

    time_taken = (time.time() - start_time) * 1000000  # 计算用时（微秒）
    return {
        "bit_length": max_int.bit_length(),  # 本机整数位数
        "max_int": max_int,  # 本机支持的最大整数
        "n": n - 1,  # 第几个斐波那契数
        "fibonacci_value": cur,  # 该斐波那契数的值
        "time_taken_ms": round(time_taken, 2),  # 计算用时（毫秒）
    }


# 4
# 递归计算斐波那契数，带时间限制
def fibonacci_memoization_with_timeout(n, memo={}, start_time=None, timeout=60):
    # 计算超时，退出递归
    if start_time is None:
        start_time = time.time()

    # 计算递归时的时间
    if time.time() - start_time > timeout:
        raise TimeoutError("计算超时，未能在限定时间内完成")

    if n in memo:
        return memo[n]

    if n <= 1:
        return n

    memo[n] = fibonacci_memoization_with_timeout(n - 1, memo, start_time, timeout) + fibonacci_memoization_with_timeout(
        n - 2, memo, start_time, timeout)

    return memo[n]


# 检查能否在1分钟内计算指定斐波那契数
# 普通递归计算斐波那契数
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


# 计算第n个斐波那契数，比较普通递归与记忆化递归的执行时间
def calculate_fibonacci_numbers(n, time_limit=5):
    result = {'error_message': "普通递归计算失败，超出时间限制。", 'memo_time': None, 'fibonacci_number': None}

    # 使用普通递归计算
    # start_time = time.time()
    # try:
    #     time.sleep(5)
    #     normal_time = time.time() - start_time
    #     if normal_time > time_limit:

    # 使用记忆化递归计算
    start_time = time.time()
    fibonacci_number_memo = fibonacci_memoization(n)
    memo_time = time.time() - start_time
    result['memo_time'] = round(memo_time, 5)
    result['fibonacci_number'] = fibonacci_number_memo

    return result


# 7
def calculate_fibonacci_binet1(n):
    """使用 Binet 公式计算第 n 个斐波那契数（不四舍五入）"""
    phi = (1 + math.sqrt(5)) / 2  # 黄金分割比
    fibonacci_value = (phi**n - (-phi)**(-n)) / math.sqrt(5)
    return fibonacci_value  # 返回浮动的小数值，不进行四舍五入


def find_min_fibonacci_no_error(epsilon):
    """找出近似公式计算斐波那契数未出现误差时的最小斐波那契数"""
    n = 1
    while True:
        real_value = calculate_fibonacci_number_iterative(n)[0]  # 实际值（通过迭代法）
        binet_value = calculate_fibonacci_binet1(n)  # Binet公式计算值
        error = abs(real_value - binet_value)  # 计算误差

        if error > epsilon:  # 判断误差是否在可接受范围内
            return n, real_value, binet_value, error  # 返回结果、Binet值及误差

        n += 1
